/*
 * File: exercise9.cpp
 * -------------------
 * 正整数的因子分解 
 * compile command :
 * g++ -Wall -g exercise9.cpp -o exercise9 -lStanfordCPPLib -I ../include/
 */

#include <iostream>
#include <cmath>
#include "simpio.h"
using namespace std;

bool is_prime(int n)
{
	if(n == 2 || n == 3)
		return true;
	int sqrtofn = std::sqrt(n);
	for(int i = 2; i <= sqrtofn; i++)
		if(n % i == 0)
			return false;
	return true;
}

void prime_factor(int n)
{
	int i;  
	//如果是质数  
	if(is_prime(n))  
	{  
		cout << n << endl;  
	}  
	else  
	{  
		for(i = 2; i <= n-1 ; ++i)  
		{  
			if(n % i == 0)  
			{  
				cout << i <<" * ";//第一个因子一定是质数  
				if(is_prime(n/i))  
				{  
					cout << n/i ;  
					break;  
				}  
				else  
				{  
					//递归调用  
					prime_factor(n/i);     
				}
				break;  
			}  
		}  
	}  
}
int main(void)
{
	cout <<"This program factors a number." <<endl;
	int i;
	while((i = getInteger("Enter a positive integer: ")) < 0)
	{
		cout<<"negative integer!"<<endl;
	}
	cout<<i<<" = ";
	prime_factor(i);
	cout<<endl;
	return 0;
}
